package hashmap

import "fmt"

type HashMapChain struct {
	// 这里使用动态数组来代替链表
	buckets     [][]*Pair
	size        int
	capacity    int
	extendRatio int
	loadTres    float64
}

func NewHashMapChain(bucketSize int) *HashMapChain {
	return &HashMapChain{
		buckets:     make([][]*Pair, bucketSize),
		size:        0,
		capacity:    bucketSize,
		extendRatio: 2,
		loadTres:    2. / 3.,
	}
}

func (a *HashMapChain) hash(k int) int {
	return (k % a.capacity)
}

func (a *HashMapChain) extend() {
	originalBucket := make([][]*Pair, a.capacity)
	for i, v := range a.buckets {
		newChainBucket := make([]*Pair, len(v))
		copy(newChainBucket, v)
		originalBucket[i] = newChainBucket
	}

	// extend
	a.capacity = a.capacity * a.extendRatio
	a.buckets = make([][]*Pair, a.capacity)
	a.size = 0
	// TODO: 这里应该使用set方法来迁移桶的数据，因为如果直接迁移，由于没有经过hash函数的重新HASH，会导致获取到的index错误
	for _, v := range originalBucket {
		for _, vv := range v {
			a.Set(vv.key, vv.val)
		}
	}

}

func (a *HashMapChain) loadFactor() float64 {
	return float64(a.size) / float64(a.capacity)
}

func (a *HashMapChain) Set(k int, v string) {
	if a.loadFactor() > a.loadTres {
		a.extend()

	}

	index := a.hash(k)
	list := a.buckets[index]
	if len(list) == 0 {
		a.buckets[index] = append(a.buckets[index], &Pair{
			key: k,
			val: v,
		})
		a.size++
		return
	}

	keyIndex := -1
	for i, vv := range list {
		if vv.key == k {
			keyIndex = i
			break
		}
	}

	if keyIndex != -1 {
		a.buckets[index][keyIndex].val = v
	} else {
		a.buckets[index] = append(a.buckets[index], &Pair{
			key: k,
			val: v,
		})
	}

}

func (a *HashMapChain) Get(k int) string {
	list := a.buckets[a.hash(k)]
	if len(list) == 0 {
		return ""
	}
	for _, v := range list {
		if v.key == k {
			return v.val
		}
	}
	return ""
}

func (a *HashMapChain) Exist(k int) bool {
	return a.Get(k) != ""
}

func (a *HashMapChain) Delete(k int) {
	list := a.buckets[a.hash(k)]
	if len(list) == 0 {
		return
	}
	for i, v := range list {
		if v.key == k {
			a.buckets[a.hash(k)] = append(a.buckets[a.hash(k)][:i], a.buckets[a.hash(k)][i+1:]...)
			a.size--
			break
		}
	}
}

func (a *HashMapChain) Keys() []int {
	var res []int
	for _, v := range a.buckets {
		if v == nil {
			continue
		}

		for _, vv := range v {
			res = append(res, vv.key)
		}
	}
	return res
}

func (a *HashMapChain) Print() {
	fmt.Printf("size: %v, capacity: %v ,loadThres: %v, extendRatio: %v \n", a.size, a.capacity, a.loadTres, a.extendRatio)
	for i, v := range a.buckets {
		if v == nil {
			continue
		}
		for _, vv := range v {
			fmt.Printf("index:%v,%d => %v \n", i, vv.key, vv.val)
		}

	}
}
